//有N件物品和一个最大容量W的背包，第i件物品的重量是weight[i],价值是value[i],每件物品只有一个，求背包最大价值
#include <vector>
#include <iostream>
#include <algorithm>
using std::vector;
using std::max;


//二维dp数组
/*
数组含义：dp[i][j]表示从下标为0-i的物品中放进容量为j的背包的价值最大值
推导方向
    1.不拿物品i，则dp[i][j]=dp[i-1][j]
    2.拿物品i，则dp[i][j]=dp[i-1][j-weight[i]]+value[i]
取最大值就是dp[i][j]
初始化dp数组：i=0，表示存放编号为0的物品，第一行能放进去就是value[0],否则0
             j=0,则背包容量为0，就是0
             其他下标可以初始化为任意值，因为会被覆盖

遍历顺序：针对01二维背包时，可以先遍历背包，也可以先遍历物品，但其他情况遍历顺序很重要
*/
int bag_2d_dp(vector<int> weight,vector<int> value,int bagWeight){
    vector<vector<int>> dp(weight.size(),vector<int>(bagWeight+1,0));

    //初始化
    for(int i=weight[0];i<=bagWeight;i++){
        dp[0][i]=value[0];
    }
    for(int i=0;i<weight.size();i++){
        dp[i][0]=0;
    }

    //推导
    for(int j=0;j<=bagWeight;j++){          //遍历背包容量（0-bagWeight)
        for(int i=1;i<weight.size();i++){  //遍历物品      (0-weight.size()-1)
            if(j<weight[i]) dp[i][j]=dp[i-1][j];        //容量不够，拿不了（没有这个会导致数组越界）
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
        }      
            
    }

    return dp[weight.size()-1][bagWeight];
}






//一维滚动数组
/*
把二维dp数组降阶为一位dp数组
条件：上一层的数据可以重复利用，复制到当前层
因为二维dp数组的递推也是依靠上一层数组（上方或左上方）
那么可以直接在上一层数组进行原地修改

因为要原地修改，就要一行一行遍历，即先遍历物品，再遍历背包，不可以改变遍历顺序
如果是先便利背包再遍历物品，就无法实现一行行滚动，一维数组无法实现
而且为了使用左上角的数据，遍历背包时应该采用倒序的方法，防止原来左上角的数据被修改（保证每个物品只取一次）


数组含义：dp[j]表示容量为j的背包所背物品的最大价值
递推公式: dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
不拿物品，还是dp[j]，拿了就是dp[j-weight[i]]+value[i]
*/
int dpfunc(vector<int> weight,vector<int> value,int bagWeight){
    //初始化数组
    vector<int> dp(bagWeight+1,0);
    for(int i=0;i<weight.size();i++){           //遍历史物品
        for(int j=bagWeight;j>=weight[i];j--){  //遍历背包，还要倒序遍历
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        } 
    }
    
    return dp[bagWeight];

}





//test
int main(){
    vector<int> weight={3,1,4};
    vector<int> value={20,15,30};
    int bagweight=4;
    std::cout<<bag_2d_dp(weight,value,bagweight)<<std::endl;
    std::cout<<dpfunc(weight,value,bagweight);
}





//416.分割等和子集
//给出一个只包含正整数的非空数组nums，是否可以将这个数组分割成两个子集，使得两个子集之和相等
/*
这个可以看成一个0-1背包问题，一个背包，装进若干数字，是否可以装到sum/2
0-1背包问题的要点：物品重量，价值，背包容量
可以求出来的是一定容量背包可装的最大价值，那么最大价值应该设为sum/2
背包的容量设为sum/2
物品的重量和价值也都设为nums[i]

这里使用一维滚动数组
*/
bool canPartition(vector<int>& nums){
    //计算总和
    int sum=0;
    for(int i=0;i<nums.size();i++){
        sum+=nums[i];
    }
    if(sum%2!=0) return false;
    int target=sum/2;

    //初始化：非零项全为0
    vector<int> dp(target+1,0);
    //先便利物品，再遍历背包，背包要倒序遍历
    for(int i=0;i<nums.size();i++){         //i是物品
        for(int j=target;j>=nums[i];j--){       //j是背包容量
            dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
        }
    }
    
    if(dp[target]==target) return true;
    return false;
}
